package org.example.algorithm.binarytree;

import org.example.algorithm.TreeNode;

import java.util.*;

/**
 * 987. 二叉树的垂序遍历
 * !!!注：行与列都相等的节点同一层可能有多个，并且不一定相邻
 */

public class VerticalOrderTraversalSolution {
    public static void main(String[] args) {
        TreeNode tree = new TreeNode(3);
        tree.left = new TreeNode(9);
        tree.right = new TreeNode(20);
        tree.right.left = new TreeNode(15);
        tree.right.right = new TreeNode(7);
        VerticalOrderTraversalSolution solution = new VerticalOrderTraversalSolution();
        System.out.println(solution.verticalTraversal(tree));
    }

    public List<List<Integer>> verticalTraversal(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        List<int[]> list = new ArrayList<>();
        dfs(root, 0, 0, list);
        list.sort((item1, item2) -> {
            if (item1[1] != item2[1]) {
                return item1[1] - item2[1];
            } else if (item1[0] != item2[0]) {
                return item1[0] - item2[0];
            } else {
                return item1[2] - item2[2];
            }
        });
        int preColumn = Integer.MAX_VALUE;
        int size = 0;
        for (int[] item: list) {
            if (item[1] != preColumn) {
                List<Integer> newList = new ArrayList<>();
                res.add(newList);
                preColumn = item[1];
                size++;
            }
            res.get(size-1).add(item[2]);
        }
        return res;
    }

    private void dfs(TreeNode root, int row, int column, List<int[]> list) {
        int[] node = new int[3];
        node[0] = row;
        node[1] = column;
        node[2] = root.val;
        list.add(node);
        if (root.left != null) {
            dfs(root.left, row+1, column-1, list);
        }
        if (root.right != null) {
            dfs(root.right, row+1, column+1, list);
        }
    }

}
